异或的期望不能直接算,对每一位单独考虑。
:节点 的第 位为 的概率。
注意经过节点 的概率不一定为 ,所以 的值不一定为 。
同理。
高斯消元得到 , 乘上该位所对应的数即为该位的期望。对所有位求和即为答案。
时间复杂度 。
注意重边和自环的处理。
#include <cmath>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
using namespace std;
#define eps 1e-8
const int MAXN = 200 , LOG = 31;
int w; double a[ MAXN + 5 ][ MAXN + 5 ];
void Gauss( ) {
for( int i = 1 ; i <= w ; i ++ ) {
int pos = i;
for( int j = i + 1 ; j <= w ; j ++ )
if( fabs( a[ pos ][ i ] ) < fabs( a[ j ][ i ] ) ) pos = j;
swap( a[ i ] , a[ pos ] );
if( fabs( a[ i ][ i ] ) < eps ) continue;
for( int j = 1 ; j <= w ; j ++ )
if( i != j ) {
double del = a[ j ][ i ] / a[ i ][ i ];
for( int k = 1 ; k <= w + 1 ; k ++ )
a[ j ][ k ] -= a[ i ][ k ] * del;
}
}
for( int i = 1 ; i <= w ; i ++ ) if( fabs( a[ i ][ i ] ) > eps ) a[ i ][ w + 1 ] /= a[ i ][ i ];
}
int n , m , deg[ MAXN + 5 ];
struct node { int v , w; node(){} node( int V , int W ) { v = V , w = W; } };
vector< node > Graph[ MAXN + 5 ];
int main( ) {
scanf("%d %d",&n,&m);
for( int i = 1 , u , v , w ; i <= m ; i ++ ) {
scanf("%d %d %d",&u,&v,&w);
deg[ u ] ++; Graph[ u ].push_back( node( v , w ) );
if( u != v ) deg[ v ] ++ , Graph[ v ].push_back( node( u , w ) );
}
w = 2 * n;
double Ans = 0;
for( int i = 0 ; i <= LOG ; i ++ ) {
memset( a , 0 , sizeof( a ) );
a[ 1 ][ w + 1 ] = 1;
for( int u = 1; u <= n ; u ++ ) {
a[ u ][ u ] = 1; a[ u + n ][ u + n ] = 1;
for( node s : Graph[ u ] )
if( s.v != n ) {
if( ( s.w >> i ) & 1 ) {
a[ u ][ s.v ] -= 0;
a[ u ][ s.v + n ] -= 1.0 / deg[ s.v ];
a[ u + n ][ s.v ] -= 1.0 / deg[ s.v ];
a[ u + n ][ s.v + n ] -= 0;
}
else {
a[ u ][ s.v ] -= 1.0 / deg[ s.v ];
a[ u ][ s.v + n ] -= 0;
a[ u + n ][ s.v ] -= 0;
a[ u + n ][ s.v + n ] -= 1.0 / deg[ s.v ];
}
}
}
Gauss();
Ans += a[ w ][ w + 1 ] * ( 1 << i );
}
printf("%.3f\n", Ans );
return 0;
}